class Node:
    def __init__(self, value):
        self.value = value
        self.lchild = None
        self.rchild = None
    
    def __repr__(self):
        return self.value


class Tree:
    def __init__(self):
        self.root = None
    
    
    def add(self, value):
        node = Node(value)
        if not self.root:
            # 如果没有根节点这个就是根节点
            self.root = node
            return 
        # 完全二叉树, 遍历查找
        queue = [self.root]
        while queue:
            index = queue.pop(0)
            if index.lchild:
                queue.append(index.lchild)
            else:
                index.lchild = node
                return
            
            if index.rchild:
                queue.append(index.rchild)
            else:
                index.rchild = node
                return
    
    def breadth_first(self):
        """
            广度优先算法
        """
        queue = [self.root]
        while queue:
            index = queue.pop(0)
            if index.lchild:
                queue.append(index.lchild)
            if index.rchild:
                queue.append(index.rchild)
            print(index.value, end=" ")
    
    def pre_order(self, node):
        """
            先序遍历
        """
        if not node:
            return ""
        print(node.value, end=" ")
        self.pre_order(node.lchild)
        self.pre_order(node.rchild)
    
    def in_order(self, node):
        """ 
            中序遍历
        """
        if not node:
            return ""
        self.in_order(node.lchild)
        print(node.value, end=" ")
        self.in_order(node.rchild)
    
    def end_order(self, node):
        """ 
            后序遍历
        """
        if not node:
            return ""
        self.end_order(node.lchild)
        self.end_order(node.rchild)
        print(node.value, end=" ")

#          1
#      2        3
#   4    5   6    7
# 8    
tree = Tree()
tree.add("1")
tree.add("2")
tree.add("3")
tree.add("4")
tree.add("5")
tree.add("6")
tree.add("7")
tree.add("8")
print("层次遍历")
tree.breadth_first()
print()
print("==========")
print("先序")
tree.pre_order(tree.root)
print()
print("==========")
print("中序")
tree.in_order(tree.root)
print()
print("==========")
print("后序")
tree.end_order(tree.root)